package offerbook;


import baseclass.a_sort.ArraysTool;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;


/**
 * Created at 2019/10/28 0028 上午 11:06
 * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
 * 打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，
 * 则打印出这三个数字能排成的最小数字为321323。
 * <p>
 * 拓展：字符串数组按照字典排序，也可以利用下面的两种算法
 * <p>
 * 方式1：对数组进行全排列，然后比较，长度为n的数组复杂度O(n!)
 * 方式2：基于比较的策略，任意两个元素m和n，有两种组合mn和nm,取min{mn,nm}
 *        其实也就是按照字典序的排序结果,时间O(n)
 * <p>
 * 考察点：
 * 1、算法
 * 2、大数问题，当数组过长，超过Integer，用String来表示大数
 * 3、算法的正确性的证明，不做要求 ，见笔记贪心1
 */
public class Code33_GetMinNumOfArrCombine {

    /**
     * 方式1：全排列后利用TreeSet排序，O(n!+n)
     *
     * @param arr
     * @return
     */
    public static String get1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return "";
        }
        //利用TreeSet自带的字典排序
        //把所有结果都加入TreeSet，返回第一个即可。
        Set<String> set = new TreeSet<>();
        process(arr, 0, set);
        set.forEach(System.out::println);
        return set.iterator().next();
    }

    private static void process(int[] arr, int index, Set<String> set) {
        if (index == arr.length - 1) {
            //全排列的结果
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]);
            }
            set.add(sb.toString());
            return;
        }
        for (int i = index; i < arr.length; i++) {
            ArraysTool.swap(arr, i, index);
            process(arr, index + 1, set);
            ArraysTool.swap(arr, index, i);
        }
    }

    private static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String o1, String o2) {
            return (o1 + o2).compareTo(o2 + o1);
        }
    }

    /**
     * 方式2
     */
    public static String get2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return "";
        }
        //优化，String是不可变的，这样赋值底层很慢，可以使用结合排序
        String[] copy = new String[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copy[i] = String.valueOf(arr[i]);
        }
//        Collections.sort(leetcode.list,new MyComparator());
        Arrays.sort(copy, (o1,o2)->(o1+o2).compareTo(o2+o1));
        StringBuilder sb = new StringBuilder();
        for (String str : copy) {
            sb.append(str);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String s = get1(new int[]{3334, 3, 3333332});
        String s1 = get2(new int[]{3, 32, 321});
        System.out.println("s = " + s);
        System.out.println("s1 = " + s1);
    }
}
